|
| creator |
Lohrey, Markus
| | Ondrusch, Nicole
| | date |
2005-03-14
| | | | description |
24 pages
| |
This paper investigates the word problem for inverse monoids
generated by a set A subject to relations of the form e=f, where e
and f are both idempotents in the free inverse monoid generated by
A. It is shown that for every fixed monoid of this form the word
problem can be solved in polynomial time which solves an open
problem of Margolis and Meakin. For the uniform word problem, where
the presentation is part of the input, EXPTIME-completeness is
shown. For the Cayley-graphs of these monoids, it is shown that the
first-order theory with regular path predicates is decidable.
Regular path predicates allow to state that there is a path from a
node x to a node y that is labeled with a word from some regular
language. As a corollary, the decidability of the generalized word
problem is deduced. Finally, it is shown that the Cayley-graph of
the free inverse monoid has an undecidable monadic second-order
theory.
| | format |
application/pdf
| | 231317 Bytes | |